(1) Field of the Invention
This invention relates to a program section layout method and a layout program and, more particularly, to a program section layout method and a layout program for a computer which runs a program while storing program sections in a cache memory.
(2) Description of the Related Art
In program execution environment using a cache memory, there has been demanded a method for storing program sections in such an arrangement as to improve space efficiency of the cache memory.
Generally, because of installation cost, a small-sized cache memory is installed as compared with a memory which stores all programs. Therefore, the program storage memory is divided by cache memory size, the cache memory is associated with the divided regions of the program storage memory, and program sections are stored in the divided regions with a prescribed algorithm. When an address is accessed for the first time, the program section of the address is copied in a corresponding region of the cache memory. Then, when the same address is accessed again, the cache memory is directly accessed. This technique realizes higher performance. When a cache miss happens because a program section to be accessed does not exist in the cache memory, the program section is copied from the program storage memory. The algorithm is designed so as to reduce cache misses.
Program sections are copied from the program storage memory into the cache memory on a prescribed size basis. Regions obtained by dividing the cache memory by this size are called cache lines. One of program sections associated with the same cache line is copied and stored in the cache memory. If different program sections associated with the same cache line are frequently accessed, the cache line is overwritten accordingly. This is called cache conflict. Many cache conflicts and cache misses slow program performance.
To solve this problem, there has been proposed a method for increasing an instruction cache hit rate in interpreter execution by dynamically changing the arrangement of an instruction cache memory on a virtual instruction basis (for example, refer to Japanese Unexamined Patent Publication No. 2000-267861, paragraphs [0023] to [0030] and FIG. 1). In addition, there has been a layout method for directly or indirectly extracting function-call patterns which possibly cause cache conflicts, and arranging programs in an order of frequently-executed functions while avoiding the patterns (for example, refer to Japanese Unexamined Patent Publication No. 2001-216140, paragraphs [0033] to [0038] and FIG. 1).
Conventional program section layout methods use various algorithms to improve space efficiency of a cache memory. These methods, however, have a drawback in which many programs should be executed to reduce cache misses, such as analyzing program structures or function call relations. This requires many kinds of algorithms and makes automation of layout of program sections difficult.
Further, when an order of program sections is determined with an algorithm, the program sections are stored in cache-size divided regions of a program storage memory in the order. A group of program sections stored in the same divided region is referred to as a section group. When a divided region for storing one section group does not have enough space to store a program section to be stored next, the program section is stored in the next divided region as a new section group. By repeating this process, the program sections belong to section groups and are stored in the program storage memory.
This technique to store program sections in divided regions in a determined order, however, has a drawback in which wasteful free regions are created because the program sections have different sizes. As a result, larger memory size is required for storing all the program sections. However, in program execution environment limiting capacity to store program sections, for example, using a read-only memory (ROM), demands for both improving space efficiency of a cache memory and decreasing the size of a region to be used for storing program sections are growing.